Relational databases are used for storage and retrieval of information. The information is structured in the database as two-dimensional tables of rows and columns. A column heading designates the type of data stored in each column. The information is stored in a non-volatile medium such as a disk array.
Users may access the database information typically by using database management software. The database storage media and management software together comprise a database management system, or DBMS. DBMSs may be implemented on a centralized mainframe system, or may be distributed in a client-server network, as examples.
The database management software includes specialized commands for accessing the database information. For example, a common command for accessing data is a Structured Query Language (SQL) xe2x80x9cselectxe2x80x9d query. Using the select query, one or more rows from one or more tables of the database may be retrieved.
The database data typically includes numbers and strings. An employee phone list, for example, may be included in a database system. More recently, spatial data, such as images, are stored along with the more traditional data. Spatial data is typically more unwieldy to manage in a database than are numbers and strings.
Traditionally, DBMSs processed queries in batch mode. In other words, a user wanting to extract information from the database would submit a query, wait a long time during which no feedback is provided, and then receive a precise answer.
One alternative to batch query processing is known as adaptive query processing. Adaptive query processing involves an iterative feedback process in which the DBMS receives information from its environment and uses the information to adapt the behavior of the query. Rather than receiving a precise answer after a long wait, an approximate answer may be received almost immediately upon submitting a query.
Database queries often invoke join operations to produce query results. Upon receiving the multi-table query, tuples, or rows, from one table are joined with tuples from a second table, to produce a result. When the tuples contain spatial data, the join operation may be prohibitively slow, in some environments.
In accordance with the embodiments described herein, a method is disclosed in which first tuples are stored in a first table and second tuples are stored in a second table in a system, the first and second tuples are partitioned into plural portions and joined based on the partitioned portions.